#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: title06最大报酬.py 
@version:
@time: 2023/05/31 
"""


def main():
    T, n = map(int, input().split())
    jobs = [list(map(int, input().split())) for _ in range(n)]
    """
    [[20, 10], [20, 20], [20, 5]]
    """
    res = solve_method(jobs, T)
    print(res)


def solve_method(jobs, t):
    if t <= 0:
        return 0
    min_time = min(jobs, key=lambda x: x[0])[0]
    # [20,10][0]
    # 20
    dp = [[0] * (t + 1) for _ in range(len(jobs) + 1)]
    # i是任务选取
    for i in range(1, len(jobs) + 1):
        # j是时间选取，从最小时间往上取
        for j in range(min_time, t + 1):
            # 取对应的job
            job = jobs[i - 1]
            # v为上一个任务的时间累计的价值
            v = dp[i - 1][j]
            # 当取的时间大于或等于前一个任务的时间，那么就拿当前任务的的价值+上一个任务的价值 与上一个任务的消耗一样时间的价值做比较
            new_v = job[1] + dp[i - 1][j - job[0]] if job[0] <= j else 0
            dp[i][j] = max(v, new_v)
    return dp[len(jobs)][t]


main()
